import java.util.*;

public class TopK {
    //前k个最大或者最小的元素，最小的用大堆，最大的用小堆，根据根节点即堆顶元素进行判断，前k个最小的即采用大根堆，
    // 堆顶元素最大，前k个最大的，即采用小根堆，堆顶元素为对内最小的。
    public static int[] topK(int[] array,int k){
        PriorityQueue<Integer> maxHeap=new PriorityQueue<>(k, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;//创建一个大小为k的大根堆，当值大于1的时候进行交换
            }
        });
        for (int i = 0; i < array.length; i++) {
            if(maxHeap.size()<k){
                maxHeap.offer(array[i]);
            }else {
                //第k+1个元素开始需要和堆顶元素进行比较
                int top=maxHeap.peek();
                if(top>array[i]){
                    //弹出元素堆顶元素
                    maxHeap.poll();
                    //加入较小的值
                    maxHeap.offer(array[i]);
                }
            }
        }
        int [] tmp=new int[k];
        for (int i = 0; i < k; i++) {
            tmp[i]=maxHeap.poll();
        }
        return tmp;
    }
    public static List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> maxHeap=new PriorityQueue<>(k, new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return (o2.get(0)+o2.get(1))-(o1.get(0)+o1.get(1));
            }
        });

        for (int i = 0; i < Math.min(nums1.length,k); i++) {
            for (int j = 0; j < Math.min(nums2.length,k); j++) {
                if(maxHeap.size()<k){
                    List<Integer> tmpList=new ArrayList<>();
                    tmpList.add(nums1[i]);
                    tmpList.add(nums2[j]);
                    maxHeap.offer(tmpList);
                }else {
                    int top=maxHeap.peek().get(0)+maxHeap.peek().get(1);
                    if(top>(nums1[i]+nums2[j])) {
                        maxHeap.poll();
                        List<Integer> tmpList = new ArrayList<>();
                        tmpList.add(nums1[i]);
                        tmpList.add(nums2[j]);
                        maxHeap.offer(tmpList);
                    }
                }

            }

        }
        List<List<Integer>> ret=new ArrayList<>();
        for (int i = 0; i <k&&!maxHeap.isEmpty() ; i++) {
            ret.add(maxHeap.poll());
        }
        return ret;

    }

    public static void main(String[] args) {
        int[] nums1={1,2};
        int[] nums2={3};
        List<List<Integer>> ret=new ArrayList<>();
        ret=kSmallestPairs( nums1,  nums2,  3);
        System.out.println(ret);
    }

    public static void main1(String[] args) {
        int[] arr={18,21,8,10,34,12};
        int[] tmp=topK(arr,2);
        System.out.println(Arrays.toString(tmp));
    }
}
